First of all you need to form an array, which contains all your primitive values, and then filter it.

Here is the function flatten() that puts all values from your structure into the flat array

const persons = [
   {
    name: 'Mr.X',
    gender: 'Male',
    location: {
      address: 'some streetname',
      zipcode: '12345',
      city: 'Berlin',
      lng: 'longitude',
      lat: 'latitude',
    },
    skills: [
     { label: 'foo' },
     { label: 'bar' },
    ],
  },
]

const flatten = (input) => {
  if (typeof input === 'object') {
    return (Array.isArray(input) ? input : Object.values(input))
      .reduce((acc, x) => acc.concat(flatten(x)), [])
  } else {
    return [input]
  } 
}

console.log(flatten(persons))
console.log(flatten(persons).includes('Berlin'))

If the results from your search are dynamically retrieved, I'd recommend adding the filtering capability to the service itself, then pass those filters in the request. This takes the load off of the client and places the responsibility on your database which is much more optimized for such a task.

If it must be entirely client-side, you can generalize the filter you have to perform comparisons on arbitrary properties.

filteredList() {
     const filterObj = {
         'name': 'Mr. X',
         'gender': 'Female'
     };

     return this.persons.filter((person) => {
       // For each of the filters defined in the filter object, determine if
       // the object passes the filter. Only take objects that pass all filters.
       let isMatch = Object.entries(filterObj).map(([key, value]) => {
           if (typeof value === 'string')
               return person[key].toLowerCase().includes(value);
           if (typeof value === 'boolean')
               return person[key] === value;
           // etc.
       }).every(i => i);

       return isMatch;
     })
},

If I understand your requirement correctly, you want to filter out with all the nested properties you have in the object with the search keyword.

Working Demo :

var vm = new Vue({
  el: '#vue-instance',
  data: {
    persons: [
       {
        name: 'Mr.X',
        gender: 'Male',
        location: {
          address: 'some streetname',
          zipcode: '12345',
          city: 'Berlin',
          lng: 'longitude',
          lat: 'latitude',
        }
      }, {
        name: 'Mrs.Y',
        gender: 'Female',
        location: {
          address: 'address 2',
          zipcode: '12345',
          city: 'alpha',
          lng: 'longitude',
          lat: 'latitude',
        }
      }
    ],
    search: ''
  },
  computed: {
    filteredList() {
       return this.persons.filter((person) => {
        const computedObj = { ...person,
            address: person.location.address,
            zipcode: person.location.zipcode,
            city: person.location.city,
            lng: person.location.lng,
            lat: person.location.lat
        }
         return Object.keys(computedObj)
              .some(key => ('' + computedObj[key]).toLowerCase().includes(this.search.toLowerCase()))
       })
    }
  }
});

<script src="https://cdnjs.cloudflare.com/ajax/libs/vue/2.5.17/vue.js"></script>
<div id="vue-instance">
  <input type="text" v-model="search" />

  <div v-for="person in filteredList" :key="person.name">
      <p>{{ person.name }}</p>
  </div>
</div>